Most computers contain a form of high performance data-storage elements called registers, which need to be used effectively to achieve high performance at runtime. The process of choosing language elements to allocate instructions to registers and the data movement required to use them is called “register allocation.” Register allocation has a major impact on the ultimate quality and performance of codes. A poor allocation can degrade both code size and runtime performance. However, finding a truly optimal solution has been proven to be computationally intractable. Several general approaches for register allocation have been proposed. For example, register allocation by graph coloring was described by Chaitin, et al. in Computer Languages, Vol. 6, pp 47-57, and in U.S. Pat. No. 4,571,678 titled “Register Allocation and Spilling via Graph Coloring.”
While there are register allocation algorithms to find good solutions in the prior art, they cannot directly apply to the machine that utilizes multiple register files having complex accessibility constraints because of the code insertion/replacement required in the register allocation to validate the code with the allocated registers. This impacts the complexity of register allocation problems in the machine.